#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int longestSubsequence(int* arr, int arrSize, int difference);
int longestSubsequence2(int* arr, int arrSize, int difference);
int compare_int(const int* o1, const int* o2);

int main()
{
	/* int arr[] = { 1, 5, 7, 8, 5, 3, 4, 2, 1 }; int res = longestSubsequence(arr, sizeof(arr) / 4, -2); */
	int arr[] = { 1, 2, 3, 4 }; int res = longestSubsequence2(arr, sizeof(arr) / 4, 1);
	printf("%d\n", res);
	return 0;
}

int longestSubsequence(int* arr, int arrSize, int difference)
{
	char* vis = calloc(arrSize, sizeof(char));

	int res = 0, layer = 0;
	for (int i = 0; i < arrSize; i++) {
		if (vis[i]) continue;
		layer = 1;
		for (int j = i + 1; j < arrSize; j++) {
			int sub = arr[j] - arr[i];
			if (sub == layer * difference) layer++, vis[j] = 1;
		}
		if (layer > res) res = layer;
	}

	return res;
}

int longestSubsequence2(int* arr, int arrSize, int difference)
{
	short dp[40010] = { 0 };
	int res = 0;
	for (int i = 0; i < arrSize; i++) {
		int val = arr[i] + 20000;
		dp[val] = dp[val + difference] + 1;
		if (dp[val] > res) res = dp[val];
	}
	return res;
}
